//反转链表 II
/*给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
ListNode* reverse(ListNode* head) {
    // if (head == NULL)
    // return NULL;
    ListNode* n1 = NULL;
    ListNode* n2 = head;
    ListNode* n3 = head->next;
    while (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    ListNode* __head = (ListNode*)malloc(sizeof(ListNode));
    ListNode* old_head = __head;
    __head->val = -1;
    __head->next = head;
    if (left == right)
        return head;
    int slow = 0;
    while (slow + 1 != left) {
        __head = __head->next;
        slow++;
    }
    ListNode* new_head = __head;
    __head = __head->next;
    slow++;
    int quick = slow;
    while (quick != right) {
        __head = __head->next;
        quick++;
    }
    ListNode* end = __head->next;
    __head->next = NULL;
    reverse(new_head->next);
    new_head->next->next = end;
    new_head->next = __head;
    return old_head->next;
}



//两数相加
/*给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    ListNode* _head = (ListNode*)malloc(sizeof(ListNode));
    _head->val = -1;
    _head->next = NULL;
    int count = 0;
    int sum = 0;
    ListNode* head = _head;
    while (l1 || l2) {
        if (l1 && l2) {
            sum = l1->val + l2->val + count;
        } else if (l1) {
            sum = l1->val + count;
        } else if (l2) {
            sum = l2->val + count;
        }
        if (sum >= 10)
            count = 1;
        else
            count = 0;

        ListNode* new = (ListNode*)malloc(sizeof(ListNode));
        new->val = sum % 10;
        new->next = NULL;
        head->next = new;
        head = head->next;
        if (l1)
            l1 = l1->next;
        if (l2)
            l2 = l2->next;
    }
    if (count) {
        sum = count;
        ListNode* new = (ListNode*)malloc(sizeof(ListNode));
        new->val = sum % 10;
        new->next = NULL;
        head->next = new;
        head = head->next;
    }
    return _head->next;
}